#ifndef TREE_H
#define TREE_H
typedef struct _tree_node
{
	struct _tree_node *left;
	struct _tree_node *right;
	void *key;
	void *data;
}TREE_NODE;

typedef struct _tree
{
	TREE_NODE *tree_link;
	unsigned keysize;
	unsigned datasize;
	unsigned count;
	int (*compare)(const void *d1,const void *d2);
}TREE;

TREE* 	tree_new(unsigned keysize,unsigned datasize,int (*compare)(const void *d1,const void *d2));
int 	tree_add(TREE *t,void *key,void *data);
void 	tree_delete(TREE *t);
void* 	tree_search(TREE *t,void *key);
void 	roll_right(TREE_NODE **node);
void 	roll_left(TREE_NODE **node);
void 	roll_min_up(TREE_NODE **node);
void 	tree_remove_node(TREE_NODE **node,void *key,int (*compare)(const void *d1,const void *d2),int *errcode);
int 	tree_remove(TREE * tree,void *key);
int 	tree_add_root(TREE *t,void *key,void *data);
int 	tree_add_spay(TREE *t,void *key,void *data);


#define RED 	0
#define BLACK 	1
typedef struct _rb_tree_node
{
	struct _rb_tree_node *left;
	struct _rb_tree_node *right;
	struct _rb_tree_node *parent;
	void *key;
	void *data;
	char color;
}RB_TREE_NODE;

typedef struct _rb_tree
{
	RB_TREE_NODE *tree_link;
	unsigned keysize;
	int datasize;
	unsigned count;
	int  (*compare)(const void *d1,const void *d2);
	void (*free_data)(void * data);
}RB_TREE;



RB_TREE* 	rb_tree_new(unsigned keysize,int datasize,int (*compare)(const void *d1,const void *d2),void (*free_data)(void *data));
int 		rb_tree_add(RB_TREE *t,void *key,void *data);
void 		rb_tree_delete(RB_TREE *t);
int			rb_tree_remove(RB_TREE *t,void* key);
#endif
